package leetcode.string;

import java.util.Arrays;

/**
 * 有一个只含有 'Q', 'W', 'E', 'R' 四种字符，且长度为 n 的字符串。
 *
 * 假如在该字符串中，这四个字符都恰好出现 n/4 次，那么它就是一个「平衡字符串」。
 *
 *  
 *
 * 给你一个这样的字符串 s，请通过「替换一个子串」的方式，使原字符串 s 变成一个「平衡字符串」。
 *
 * 你可以用和「待替换子串」长度相同的 任何 其他字符串来完成替换。
 *
 * 请返回待替换子串的最小可能长度。
 *
 * 如果原字符串自身就是一个平衡字符串，则返回 0。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：s = "QWER"
 * 输出：0
 * 解释：s 已经是平衡的了。
 * 示例 2：
 *
 * 输入：s = "QQWE"
 * 输出：1
 * 解释：我们需要把一个 'Q' 替换成 'R'，这样得到的 "RQWE" (或 "QRWE") 是平衡的。
 * 示例 3：
 *
 * 输入：s = "QQQW"
 * 输出：2
 * 解释：我们可以把前面的 "QQ" 替换成 "ER"。
 * 示例 4：
 *
 * 输入：s = "QQQQ"
 * 输出：3
 * 解释：我们可以替换后 3 个 'Q'，使 s = "QWER"。
 *  
 *
 * 提示：
 *
 * 1 <= s.length <= 10^5
 * s.length 是 4 的倍数
 * s 中只含有 'Q', 'W', 'E', 'R' 四种字符
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/replace-the-substring-for-balanced-string
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class 替换子串获取平衡字符串 {

    /**
     * qwer 0123
     * 固定窗口 时间复杂度高
     */
    static class Solution_1 {
        public int balancedString(String s) {
            char[] ss = s.toCharArray();
            int[] nums = new int[4];
            for (char i : ss){
                switch (i){
                    case 'Q': nums[0]++;break;
                    case 'W': nums[1]++;break;
                    case 'E': nums[2]++;break;
                    case 'R': nums[3]++;break;
                }
            }
            int p = (nums[0] + nums[1] + nums[2] + nums[3]) / 4;
            int[] need = new int[]{ nums[0]>p ? nums[0]-p:0, nums[1]>p ? nums[1]-p:0, nums[2]>p ? nums[2]-p:0, nums[3]>p ? nums[3]-p:0};
            int min = 0;
            for (int i : need){
                min += i;
            }
            if (min == 0){
                return 0;
            }else {
                for (int n = min; n < ss.length; n++){
                    for (int i = 0; i+n <= ss.length; i++){
                        int[] tmp = need.clone();
                        for (int j = i; j < i+n; j++){
                            switch (ss[j]) {
                                case 'Q':
                                    tmp[0]--;
                                    break;
                                case 'W':
                                    tmp[1]--;
                                    break;
                                case 'E':
                                    tmp[2]--;
                                    break;
                                case 'R':
                                    tmp[3]--;
                                    break;
                            }
                            boolean flag = true;
                            for (int k : tmp){
                                if (k > 0) flag = false;
                            }
                            if (flag) return n;
                        }
                    }
                }
            }
            return 0;
        }
    }

    /**
     * 不固定大小 先确定right位置 然后移动left 当不符合条件时 再移动right
     */
    static class Solution {
        public int balancedString(String s) {
            if(s==null || s.length()<=0) return -1;
            int N=s.length();
            // 这里用26有的浪费,为了方便写代码,就这样吧
            int[] need=new int[26];
            // 初始化为-N/4这样最后得到的大于0的值就是多出来的
            Arrays.fill(need,-N/4);
            int[] cur=new int[26];
            for(int i=0;i<N;i++){
                need[s.charAt(i)-'A']++;
            }
            // 有几个字符多出来了
            int needCount=0;
            for(int i=0;i<need.length;i++){
                if(need[i]>0) needCount++;
            }
            if(needCount==0) return 0;
            int res=N;
            int left=0,right=0;
            int matchCount=0;
            // 滑窗
            while(right<s.length()){
                char c=s.charAt(right);
                if(need[c-'A']>0){
                    cur[c-'A']++;
                    if(cur[c-'A']==need[c-'A']){
                        matchCount++;
                    }
                }
                while(left<=right && matchCount==needCount){
                    res=Math.min(right-left+1,res);
                    char cl=s.charAt(left);
                    if(need[cl-'A']>0){
                        cur[cl-'A']--;
                        if(cur[cl-'A']<need[cl-'A']){
                            matchCount--;
                        }
                    }
                    left++;
                }
                right++;
            }
            return res;
        }
    }

    public static void main(String[] args){
        Solution s = new Solution();
        System.out.println(s.balancedString("QWERQQRR"));
    }
}
